The problem of associating sets of observations from two sensor systems in the presence of bias, random errors, false alarms, and misdetections is fundamental in multi-sensor tracking systems. For example, if two sensor systems are tracking a plurality of airplanes, each sensor system develops tracks based on what is seen in the sky. One tracking system may want to share data with the other system and transmits its current picture of what it sees to the other system. The second system must determine what it has received from the first system. In particular, it must determine which data points received from the first sensor system correspond to the airplanes it is tracking in its current system. This is difficult because each sensor system has associated error, which makes it difficult to assign a data point from one sensor system to the other. Examples of errors may include misalignment between the two sensor systems, different levels of tolerances, and the fact that one system may see certain airplanes that the other does not. As described above, each particular system may have errors due to bias, random errors, false alarms, and misdetections. Therefore it is difficult to simply use a set of data received from the first sensor system and overlay it with the second sensor system.
Common approaches to this problem are described in Blackman, S. and R. Popoli, Design and Analysis of Modern Tracking Systems, Artech House, Norwood, Mass., 1999. In general, these methods involve separate steps to first determine and correct for persistent bias within either of the sensor systems. Persistent bias refers to a consistent bias, such as incorrectly measuring a distance by the same distance each time. The second step is to perform an optimal assignment of the two sets of data, which are now assumed to include only random errors. This second step of optimally assigning the two sets of data is referred to as the global nearest neighbor (GNN) problem, and is commonly solved using either Bertsekas's auction algorithm, as described in Bertsekas, D. P., “The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial,” Interfaces, Vol. 20, pp. 133–149, 1990, or a JVC algorithm to minimize assignment costs based upon Mahalanobis (or chi-square) distances between the observations after bias removal. The JVC algorithm is described in Drummond, O. E., D. A. Castanon and M. S. Bellovin, “Comparison of 2-D Assignment Algorithms for Rectangular, Floating Point Cost Matrices,” Proc. of SDI Panels on Tracking, No. 4, pp. 81–97, December 1990, and Jonker, R. and A. Volgenant, “A Shortest Augmenting Path Algorithms for Dense and Sparse Linear Assignment Problems,” Computing, Vol. 39, pp. 325–340, 1987.
A problem with these approaches is that the global nearest neighbor problem assumes alignment between the two sensor systems is good such that (i) errors between observations of the sensor system of the same object are purely random (Gaussian distributed), and (ii) errors and observations of one object are completely independent of errors and observations of other objects. However, because of these assumptions, this approach does not address a persistent bias, also referred to as registration error, between the two sensor systems, which is often actually the case. For example, a first measurement system might be rotated 30 degrees off of a second measurement system. The global nearest neighbor formulation works best when both systems hold observations on the same objects and can tolerate large biases in this restrictive circumstance. In the more realistic case wherein each system holds some observations the other lacks, the global nearest neighbor formulation works well only if there are no bias errors. Many techniques exist to determine and remove the bias errors prior to attempting assignment. Often, these use comparison of observations on well separated airplanes where the correct assignment is unambiguous.
Image processing techniques have also been applied to the problem of assigning sets of observations from two sensor systems. In that approach, each set of data is treated as an image and a peak correlation is attempted to be found using a Fast Fourier transform and convolutions. This results in a bias between the two systems. The bias is removed and the unbiased problem is solved using the GNN approach described above. However, in this approach the bias is cured independent of making assignments and is therefore not necessarily calculated appropriately. As a result, one cannot show that the determined solution is a maximum likelihood solution.
In Kenefic, R. J., “Local and Remote Track File Registration Using Minimum Description Length,” IEEE Trans. on Aerospace and Electronic Systems, Vol. AES-29, No. 3, July 1993, pp. 651–655, Kenefic postulated a formulation of the observation assignment problem that incorporates a cost function that accounts for both bias and random errors together. However, Kenefic offered no efficient algorithm to solve the problem.